/*
题目: 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
https://leetcode.cn/problems/minimum-window-substring/
 */
public class MinWindow {
    public String minWindow(String s, String t) {
        //滑动窗口
        int sLen = s.length(), tLen = t.length();
        if (sLen < tLen) {
            return new String();
        }
        Map<Character, Integer> window = new HashMap<> ();
        Map<Character, Integer> target = new HashMap<> ();

        for (int i = 0; i < tLen; i++) {
            window.put(s.charAt(i), window.getOrDefault(s.charAt(i), 0) + 1);
            target.put(t.charAt(i), target.getOrDefault(t.charAt(i), 0) + 1);
        }
        Set<Map.Entry<Character, Integer>> resultSet = target.entrySet(); //将Key-Value转化成Set集合
        if (check(window, resultSet)) {
            return s.substring(0, tLen); //这时候匹配, 就是是最短的
        }

        int resLen = 2147483647; //记录涵盖t字符串的最短长度
        int ansLeft = 0, ansRight = -1; //-1代表没有更新过
        int left = 0; //滑动窗口左边界
        for (int i = tLen; i < sLen; i++) {
            char curr = s.charAt(i);
            window.put(curr, window.getOrDefault(curr, 0) + 1);

            //如果涵盖t字符串, 那就一直压缩
            while (check(window, resultSet)) {
                if (i - left + 1 < resLen) {
                    resLen = i - left + 1;
                    ansRight = i + 1;
                    ansLeft = left;
                }
                curr = s.charAt(left);
                window.put(curr, window.get(curr) - 1);
                left++;
            }
        }
        return ansRight == -1 ? new String() : s.substring(ansLeft, ansRight);
    }

    //判断当前窗口 是否涵盖了t字符串
    private boolean check(Map<Character, Integer> window, Set<Map.Entry<Character, Integer>> resultSet) {
        for (Map.Entry<Character, Integer> entry : resultSet) {
            Character curKey = entry.getKey();
            Integer curValue = entry.getValue();
            if (window.getOrDefault(curKey, 0) < curValue) { //缺少某些字符
                return false;
            }
        }
        return true;
    }
}
